package com.yubest;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 * <p>
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
 * 示例 2：
 * <p>
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
 *      注意，你可以重复使用字典中的单词。
 * 示例 3：
 * <p>
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 300
 * 1 <= wordDict.length <= 1000
 * 1 <= wordDict[i].length <= 20
 * s 和 wordDict[i] 仅有小写英文字母组成
 * wordDict 中的所有字符串 互不相同
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2022/1/17 11:22
 */
public class P0139 {

    public static void main(String[] args) {
        System.out.println(new Solution139().wordBreak("aaaaaaa", Arrays.asList("aaaa", "aa")));
    }
}

class Solution139 {

    /**
     * todo 超时
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        Trie139 trie = new Trie139();
        for (String s1 : wordDict) {
            trie.insert(s1);
        }
        return match(s, 0, trie.root, trie.root);
    }

    private boolean match(String s, int index, TrieNode139 node, TrieNode139 root) {
        if (index >= s.length()) {
            return true;
        }
        TrieNode139 cur = node.get(s.charAt(index));
        if (null == cur) {
            return false;
        }
        if (index == s.length() - 1 && !cur.end) {
            return false;
        }
        if (cur.end) {
            return match(s, index + 1, cur, root) || match(s, index + 1, root, root);
        }
        return match(s, index + 1, cur, root);
    }
}

class Trie139 {

    TrieNode139 root;

    public Trie139() {
        root = new TrieNode139('/');
    }

    public void insert(String word) {
        int n = word.length();
        TrieNode139 cur = root;
        char c;
        for (int i = 0; i < n; i++) {
            c = word.charAt(i);
            if (cur.containsKey(c)) {
                cur = cur.get(c);
            } else {
                cur = cur.put(c, new TrieNode139(c));
            }
            if (i == n - 1) {
                cur.end = true;
            }
        }
    }
}

class TrieNode139 {
    char val;
    boolean end;
    Map<Character, TrieNode139> children = new HashMap<>();

    TrieNode139(char val) {
        this(val, false);
    }

    TrieNode139(char val, boolean end) {
        this.val = val;
        this.end = end;
    }

    boolean containsKey(Character key) {
        return children.containsKey(key);
    }

    TrieNode139 get(Character key) {
        return children.get(key);
    }

    TrieNode139 put(Character key, TrieNode139 node) {
        children.put(key, node);
        return node;
    }
}
